package org.hhchat.leetcode.sort;

import org.hhchat.leetcode.dataStruct.Interval;

import java.util.LinkedList;
import java.util.List;

/**
 * Created this one by HMH on 2017/5/29.
 * leetcode里面一个o(n)的答案。。。
 * 一个个扫描过去，切掉无关的，一个个融合进最新的，直到再次无关，添加到集合中
 */
public class code57 {
    public class Solution {
        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            List<Interval> result = new LinkedList<>();
            int i = 0;
            // add all the intervals ending before newInterval starts
            while (i < intervals.size() && intervals.get(i).end < newInterval.start)
                result.add(intervals.get(i++));
            // merge all overlapping intervals to one considering newInterval
            while (i < intervals.size() && intervals.get(i).start <= newInterval.end) {
                newInterval = new Interval( // we could mutate newInterval here also
                        Math.min(newInterval.start, intervals.get(i).start),
                        Math.max(newInterval.end, intervals.get(i).end));
                i++;
            }
            result.add(newInterval); // add the union of intervals we got
            // add all the rest
            while (i < intervals.size()) result.add(intervals.get(i++));
            return result;
        }
    }

}
